The present invention relates to a circuit for translating an address in a computer system using a virtual storage method.
A processor to support a virtual storage requires an address translation circuit for translating a logical address into a physical address. As such an address translation method, a segmentation/paging composite method is applied to a case where a large logical space is used. In this method, for example, the logical space is divided into several segments and each segment is further subdivided into a plurality of pages. There are disposed a segment table ST and a page table PT (these tables are referred to as translation tables) to indicate whether a particular page in a particular segment exists in the main storage or not and when they are found to be present, indicate their physical addresses in the main storage. Thus, the address translation in this method is achieved through a 2-stage translation by use of these two tables. This provision is adopted because it will increase the amount of the hardware elements to provide a table which establishes a one-to-one correspondence between all logical addresses in the logical space and the physical addresses.
Referring now to FIG. 1 which is an explanatory diagram of the segmentation/paging composite method, the segmentation/paging composite method will be explained.
The segment table ST and the page table PT are provided in the main storage. A segment table origin register STOR provided in the address translation mechanism is used to store the top address STTOP of the segment table ST. By accessing an address in the segment table assigned or specified by the top address STTOP and the SEG field of a specified logical address LA, that top address PTTOP of the page table PT which corresponds to the segment (SEG) field of the logical address LA is read and then the obtained top address PTTOP is set in a page table register (not shown) provided in the address translation mechanism. Subsequently, by accessing an address in the page table PT assigned or specified by the content of the page table register and the page field PAGE of the logical address, the top address PAGETOP of the page corresponding to the page field PAGE of the logical address LA is read. This read PAGETOP is the upper-order portion of the physical address. The lower-order portion OFFSET of the logical address LA is the lower-order portion of the physical address as it is. Thus, the physical address can be obtained by combining the PAGETOP and lower-order portion OFFSET of the logical address LA. However, in this address translation method, the tables ST and PT are accessed to translate a logical address into a physical address, namely, the main storage is twice accessed, which results in a time-consuming address translation.
To overcome this, there can be considered an address translation method using a high-speed translation buffer or translation lookaside buffer (TLB) which functions like the translation table.
FIG. 2 is an explanatory diagram of an address translation method using such a TLB, and FIG. 3 shows an example of the logical address in this case. Namely, the logical address 67 of this example includes an upper-order portion LAU (17 bits), an intermediate portion LAM (3 bits), and a lower-order portion OFFSET (12 bits): Although the TLB 60 comprises eight entries corresponding to 3-bit LAM, only one entry is shown in the TLB 60 of FIG. 2. In each entry are registered the upper-order LAU of the logical address and the PAGETOP respectively corresponding to the top addresses of the segment and the page for an instruction or operand which was recently accessed and exists in the main storage. When the main storage is to be accessed, in order to determine whether or not the inputted logical address 67 exists in the TLB, the TLB is read to obtain an entry corresponding to the LAM of the logical address 67. The LAU 62 in the entry is then compared with the LAU 64 of the accessed logical address 67 by means of a comparator 61 whether they are identical (to be referred to as a TLB hit hereafter) or not identical (to be referred to as a TLB mishit). If a hit results, the PAGETOP in the entry and the OFFSET 66 of the accessed logical address 67 are combined to generate a physical address 68. In the case of TLB mishit, since this PAGETOP is invalid, the address translation is accomplished according to the address translation method of FIG. 1 to obtain the LAU and the PAGETOP, which in turn are registered to an entry of the TLB. Consequently, TLB hit results for the subsequent access to the pertinent address. In this method, the main storage is not accessed in the case of TLB hit, and hence the address translation can be performed at a higher speed as compared with the method of FIG. 1.
FIG. 4 shows a method using one TLB described above. This method has been proposed in the JP-A-61-217846 laid-open on Sept. 27, 1986 (Japanese Patent Application No. 60-57576 filed on Mar. 23, 1985 in the name of the same assignee of the present application). The operation of this translation method is the same as the operation described in conjunction with FIG. 2. But, it is to be noted here that, in FIG. 4, the LAU 64 of the logical address 67 and the data bus 69 are inputted to the TLB. This is because the LAU and the PAGETOP corresponding to the data read from the main storage are to be registered to the TLB 60 when TLB mishit occurs.
FIG. 5 shows an example using two TLB's similar to that described in the JP-B-1658 and the like. Although the method for selecting an entry of the TLB is the same as in he case of one TLB scheme, since two TLB's are used in this method, two comparators 72 and 73 are necessary for the judgment of TLB hit by comparing the LAU's 76 and 78 respectively registered to the TLB's 70 and 71 with the LAU 64 of the logical address 67 to be accessed. Further, there must be also provided a selector 75 for determining, based on the comparison results 80 and 81, which one of TLB's is indicating the TLB hit and selecting the PAGETOP 77 or 79 registered in the TLB which shows the TLB hit and a control circuit 74 for outputting a select signal 82 to control the selector 75. If hit does not occur in the TLB 70 nor in the TLB 71, the translation method of FIG. 1 is also executed and after the translation, for the registration of the entry to the TLB, LRU control method or the like is used, namely, an entry to which data has been more previously registered and which contains the old contents (LAU, PAGETOP, etc.) is updated with new contents.
The above-mentioned schemes using one or two TLB's have the following problems. Assume in the 1-TLB method of FIG. 4 that the logical address is represented by 8 hexadecimal characters and that the 5th character from the most significant bit thereof is an intermediate section LAM used to select an entry of the TLB as shown in FIG. 6. If a logical address at which an instruction is stored in the main storage is 3E503000, the entry number of the TLB is 3. Further, assuming that data to be used by the instruction is stored at a logical address 6F253000, the entry number of the TLB is also 3, which means that the instruction area and the data area use the same entry of the TLB. In such a case, when the instruction cycle and the operand cycle are alternately executed, mishit occurs repetitiously, which leads to a problem that the hit rate is abruptly lowered.
On the other hand, in the 2-TLB method of FIG. 5, the situation associated with the problem of the 1-TLB method does not cause any problem because of two TLB's. In this method however, until the judgment of the TLB hit is finished for both TLB's, selection of one PAGETOP to be used as a part of the physical address out of two PAGETOP's registered in the TBL's must be deffered. Consequently, the speed of the address translation to obtain the physical address is lowered when compared with the 1-TLB method. Moreover, since a comparator is necessary for each TLB, there arises a problem that the amount of hardware elements is increased as compared with the 1-TLB method.